package Demo1021;

import java.util.Arrays;

/**
 * 快速排序
 * @author Knife
 */
public class QuickSort {
    public static void main(String[] args) {
        int [] arr = new int[]{5,8,9,1,2,3,4,7,6};
        quick(arr,0,arr.length-1);
    }
    public static void quick(int [] arr, int l, int h){
        if (l>=h){
            return;
        }
        int p = partition(arr, l, h);
        quick(arr,l,p-1);
        quick(arr,p+1,h);
    }
    public static int partition(int [] arr, int l, int h){
        int pv = arr[h];
        int i = l;
        for (int j = l; j < arr.length - 1; j++) {
            if (arr[j] < pv){
                if (i!=j){
                    swap(arr,i,j);
                }
                i++;
            }
        }
        if (i!=h){
            swap(arr,i,h);
        }

        System.out.println(Arrays.toString(arr)+",i="+i);
        return i;
    }

    public static void swap(int[] arr,int i,int j){
        int temp ;
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
